import java.util.Arrays;

public class InsertSort {
    private int[] array;

    public InsertSort(int[] array) {
        this.array = array;
    }

    public void zhijieinsertSort() {
        zhebancharu(array);
    }
    public void xierinsertSort(){
        xiersort(array);
    }

    public void print() {
        System.out.println(Arrays.toString(array));
    }

    private void zhebancharu(int[] a) {
        int n = a.length;
        int i, j, temp, low, high, mid;
        for (i = 1; i < n; i++) {
            low = 0;
            high = i - 1;
            if (a[i] < a[i - 1]) {
                temp = a[i];
                while (low <= high) {
                    mid = (low + high) / 2;
                    if (temp >= a[mid]) low = mid + 1;
                    else high = mid - 1;
                }
                for (j = i - 1; j >= low && a[j] > temp; j--) {
                    a[j + 1] = a[j];
                }
                a[j + 1] = temp;
            }
        }
    }
    private void xiersort(int[] a){
        int n=a.length;
        int i,j,d,tmp;
        for(d=n/2;d>=1;d/=2 ){
            for (i = d; i < n; i++) {
                if(a[i]<a[i-d]){
                    tmp=a[i];
                    for (j = i-d; j >= 0&&a[j]>tmp; j-=d) {
                        a[j+d]=a[j];
                    }
                    a[j+d]=tmp;
                }

            }
        }
    }
}

